package solution;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Generate {
    public static List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ret = new ArrayList<>();
        // 先添加第一行，节省后续的代码
        List<Integer> row = new LinkedList<>();
        row.add(1);
        ret.add(row);
        // 外层循环
        for (int i = 1; i < numRows; i++) {
            List<Integer> prevRow = new LinkedList<>(ret.get(i - 1));
            List<Integer> curRow = new LinkedList<>();
            // 内层循环
            for (int j = 0; j <= i; j++) {
                if(j == 0 || j == i) {
                    // 第一个或者最后一个
                    curRow.add(1);
                } else {
                    //中间的
                    curRow.add(prevRow.get(j - 1) + prevRow.get(j));
                }
            }
            ret.add(curRow);
        }
        return ret;
    }

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();

        generate(5);
    }
}
